{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Path Cost in a Hidden Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #interactive #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #交互 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findShortestPath"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #隐藏网格下的最小消耗路径"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>这是一个交互问题。</p>\n",
    "\n",
    "<p>有一个机器人存在于网格中，你需要通过不断尝试使他从初始单元到达目标单元。网格的规格为m x n，并且每个单元的属性值要不为空，要不已被占用。题目<strong>保证</strong>初始网格和目标网格不同且均为空。</p>\n",
    "\n",
    "<p>每个单元格都有<b>消耗</b>值，你需要在每次<strong>移动</strong>至此单元格后支付该费用。在机器人启动前，初始单元的费用不被计算在内。</p>\n",
    "\n",
    "<p>你需要找到机器人移动至目标网格的最小总消耗。但可惜的是你并<strong>不知道</strong>网格的尺寸、初始单元和目标单元。你只允许通过询问<code>GridMaster</code>类获得信息。</p>\n",
    "\n",
    "<p><code>GridMaster</code>类存在以下功能：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>boolean canMove(char direction)</code> 当机器人可以向这个方向移动时，返回<code>true</code>；反之返回<code>false</code>。</li>\n",
    "\t<li><code>int move(char direction)</code> 沿该方向移动机器人，并返回移动到该单元的消耗值。如果此移动将机器人移动到被占有的单元格或离开网格，则移动将被<strong>忽略</strong>，机器人将保持在相同的位置，函数将返回<code>-1</code>。</li>\n",
    "\t<li><code>boolean isTarget()</code> ：如果机器人当前位于目标单元格上，则返回<code>true</code>；<span style=\"\">反之返回</span> <code>false</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请注意，上述函数中的方向应该是<code>{ 'U'、'D'、'L'、'R' }</code>中的字符，分别表示向上、向下、左和右方向。</p>\n",
    "\n",
    "<p>返回使机器人从其初始起始单元到目标单元的<strong>最小总消耗</strong>。如果单元格之间不存在有效路径，则返回<code>-1</code>。</p>\n",
    "\n",
    "<p><strong>测试实例:</strong></p>\n",
    "\n",
    "<p>测试输入一个大小为<code>m x n</code>的二维数组 <code>grid</code> 和四个<code>int</code>型参数 <code>r1</code>, <code>c1</code>, <code>r2</code>, 和 <code><font face=\"monospace\">c2</font></code> :</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>grid[i][j] == 0</code> 表示网格 <code>(i, j)</code> 已被占用。</li>\n",
    "\t<li><code>grid[i][j] >= 1</code> 表示网格单元 <code>(i, j)</code> 为空并且 <code>grid[i][j]</code> 的值为移动至此网格的成本值。</li>\n",
    "\t<li><code>(r1, c1)</code> 为初始单元。</li>\n",
    "\t<li><code>(r2, c2)</code> 为目标单元。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请注意，你将无法在你的代码中获知这些信息。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[2,3],[1,1]], r1 = 0, c1 = 1, r2 = 1, c2 = 0\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong> 其中一种可能路径描述如下：\n",
    "机器人最开始站在单元格 (0, 1) ，用 3 表示\n",
    "- master.canMove('U') 返回 false\n",
    "- master.canMove('D') 返回 true\n",
    "- master.canMove('L') 返回 true\n",
    "- master.canMove('R') 返回 false\n",
    "- master.move('L') 机器人移动到单元格 (0, 0) 并返回 2\n",
    "- master.isTarget() 返回 false\n",
    "- master.canMove('U') 返回 false\n",
    "- master.canMove('D') 返回 true\n",
    "- master.canMove('L') 返回 false\n",
    "- master.canMove('R') 返回 true\n",
    "- master.move('D') 机器人移动到单元格 (1, 0) 并返回 1\n",
    "- master.isTarget() 返回 true\n",
    "- master.move('L') 机器人不移动并返回 -1\n",
    "- master.move('R') 机器人移动到单元格 (1, 1) 并返回 1\n",
    "现在我们知道了机器人达到目标单元(1, 0)的最小消耗成本为2。 </pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[0,3,1],[3,4,2],[1,2,0]], r1 = 2, c1 = 0, r2 = 0, c2 = 2\n",
    "<strong>输出:</strong> 9\n",
    "<strong>解释:</strong> 最小消耗路径为 (2,0) -> (2,1) -> (1,1) -> (1,2) -> (0,2).\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> grid = [[1,0],[0,1]], r1 = 0, c1 = 0, r2 = 1, c2 = 1\n",
    "<strong>输出:</strong> -1\n",
    "<strong>解释:</strong> 不存在可使机器人到达目标单元的路径。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= n, m <= 100</code></li>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>0 <= grid[i][j] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-path-cost-in-a-hidden-grid](https://leetcode.cn/problems/minimum-path-cost-in-a-hidden-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-path-cost-in-a-hidden-grid](https://leetcode.cn/problems/minimum-path-cost-in-a-hidden-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,3],[1,1]]\\n0\\n1\\n1\\n0', '[[0,3,1],[3,4,2],[1,2,0]]\\n2\\n0\\n0\\n2', '[[1,0],[0,1]]\\n0\\n0\\n1\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is GridMaster's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class GridMaster(object):\n",
    "#    def canMove(self, direction: str) -> bool:\n",
    "#        \n",
    "#\n",
    "#    def move(self, direction: str) -> int:\n",
    "#        \n",
    "#\n",
    "#    def isTarget(self) -> None:\n",
    "#        \n",
    "#\n",
    "\n",
    "class Solution(object):\n",
    "    def findShortestPath(self, master: 'GridMaster') -> int:\n",
    "        move = {\n",
    "            'U':('D',-1,0),\n",
    "            'D':('U',1,0),\n",
    "            'L':('R',0,-1),\n",
    "            'R':('L',0,1)}\n",
    "        grid_dic = defaultdict(int)\n",
    "        end = ()\n",
    "        def dfs(grid,r,c):\n",
    "            nonlocal end\n",
    "            if grid.isTarget():\n",
    "                end = (r,c)\n",
    "            for u,value in move.items():\n",
    "                out,x,y = value\n",
    "                if grid.canMove(u) and (r+x,c+y) not in grid_dic:\n",
    "                    num = grid.move(u)\n",
    "                    grid_dic[(r+x,c+y)] = num\n",
    "                    dfs(grid,r+x,c+y)\n",
    "                    grid.move(out)\n",
    "        dfs(master,0,0)\n",
    "        if end not in grid_dic:\n",
    "            return -1\n",
    "        visited = {(0,0):0}\n",
    "        heap = [[0,0,0]]\n",
    "        while heap:\n",
    "            res,r,c = heapq.heappop(heap)\n",
    "            if (r,c) == end:\n",
    "                return res\n",
    "            for _,x,y in move.values():\n",
    "                index = (r+x,c+y)\n",
    "                if index in grid_dic and index not in visited:\n",
    "                    cnt = res+grid_dic[index]\n",
    "                    visited[index] = cnt\n",
    "                    heapq.heappush(heap,[cnt,index[0],index[1]])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is GridMaster's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class GridMaster(object):\n",
    "#    def canMove(self, direction: str) -> bool:\n",
    "#        \n",
    "#\n",
    "#    def move(self, direction: str) -> int:\n",
    "#        \n",
    "#\n",
    "#    def isTarget(self) -> None:\n",
    "#        \n",
    "#\n",
    "\n",
    "class Solution(object):\n",
    "    def findShortestPath(self, master: 'GridMaster') -> int:\n",
    "        move = {\n",
    "            'U':('D',-1,0),\n",
    "            'D':('U',1,0),\n",
    "            'L':('R',0,-1),\n",
    "            'R':('L',0,1)}\n",
    "        grid_dic = defaultdict(int)\n",
    "        end = ()\n",
    "        def dfs(grid,r,c):\n",
    "            nonlocal end\n",
    "            if grid.isTarget():\n",
    "                end = (r,c)\n",
    "            for u,value in move.items():\n",
    "                out,x,y = value\n",
    "                if grid.canMove(u) and (r+x,c+y) not in grid_dic:\n",
    "                    grid_dic[(r+x,c+y)] = grid.move(u)\n",
    "                    dfs(grid,r+x,c+y)\n",
    "                    grid.move(out)\n",
    "        dfs(master,0,0)\n",
    "        if end not in grid_dic:\n",
    "            return -1\n",
    "        visited = {(0,0):0}\n",
    "        heap = [[0,0,0]]\n",
    "        while heap:\n",
    "            res,r,c = heapq.heappop(heap)\n",
    "            if (r,c) == end:\n",
    "                return res\n",
    "            for _,x,y in move.values():\n",
    "                index = (r+x,c+y)\n",
    "                if index in grid_dic and index not in visited:\n",
    "                    cnt = res+grid_dic[index]\n",
    "                    visited[index] = cnt\n",
    "                    heapq.heappush(heap,[cnt,index[0],index[1]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is GridMaster's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class GridMaster(object):\n",
    "#    def canMove(self, direction: str) -> bool:\n",
    "#        \n",
    "#\n",
    "#    def move(self, direction: str) -> int:\n",
    "#        \n",
    "#\n",
    "#    def isTarget(self) -> None:\n",
    "#        \n",
    "#\n",
    "\n",
    "class Solution(object):\n",
    "    def findShortestPath(self, master: 'GridMaster') -> int:\n",
    "        move = {\n",
    "            'U':('D',-1,0),\n",
    "            'D':('U',1,0),\n",
    "            'L':('R',0,-1),\n",
    "            'R':('L',0,1)}\n",
    "        S = {\n",
    "            'U':'↑',\n",
    "            'D':'↓',\n",
    "            'L':'←',\n",
    "            'R':'→'}\n",
    "        grid_dic = defaultdict(int)\n",
    "        end = ()\n",
    "        def dfs(grid,r,c):\n",
    "            nonlocal end\n",
    "            if grid.isTarget():\n",
    "                end = (r,c)\n",
    "            for u,value in move.items():\n",
    "                out,x,y = value\n",
    "                if grid.canMove(u) and (r+x,c+y) not in grid_dic:\n",
    "                    num = grid.move(u)\n",
    "                    grid_dic[(r+x,c+y)] = num\n",
    "                    dfs(grid,r+x,c+y)\n",
    "                    grid.move(out)\n",
    "        dfs(master,0,0)\n",
    "        #for k,v in grid_dic.items():\n",
    "        #    print(k,v)\n",
    "        #print(end)\n",
    "        #print(grid_dic)\n",
    "        if end not in grid_dic:\n",
    "            return -1\n",
    "        visited = {(0,0):0}\n",
    "        heap = [[0,0,0,'']]\n",
    "        while heap:\n",
    "            res,r,c,s = heapq.heappop(heap)\n",
    "            if (r,c) == end:\n",
    "                #print(s)\n",
    "                return res\n",
    "            for _,x,y in move.values():\n",
    "                index = (r+x,c+y)\n",
    "                if index in grid_dic and index not in visited:\n",
    "                    cnt = res+grid_dic[index]\n",
    "                    visited[index] = cnt\n",
    "                    heapq.heappush(heap,[cnt,index[0],index[1],s+S[move[_][0]]])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is GridMaster's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class GridMaster(object):\n",
    "#    def canMove(self, direction: str) -> bool:\n",
    "#        \n",
    "#\n",
    "#    def move(self, direction: str) -> int:\n",
    "#        \n",
    "#\n",
    "#    def isTarget(self) -> None:\n",
    "#        \n",
    "#\n",
    "\n",
    "class Solution(object):\n",
    "    def findShortestPath(self, master: 'GridMaster') -> int:\n",
    "        def dfs(i, j):\n",
    "            nonlocal grid, directions, visited, findtarget, endx, endy\n",
    "\n",
    "            visited.add((i, j))  # 加入已经访问\n",
    "            if master.isTarget(): # 目标位置\n",
    "                endx, endy = i, j\n",
    "                findtarget = True\n",
    "\n",
    "            for dx, dy, d, revd in directions:\n",
    "                if (i+dx, j+dy) not in visited and master.canMove(d):\n",
    "                    grid[i+dx][j+dy] = master.move(d) # 记录成本\n",
    "                    dfs(i+dx, j+dy)\n",
    "                    master.move(revd) # 回溯\n",
    "            return\n",
    "\n",
    "        grid = [[0 for _ in range(201)] for _ in range(201)]\n",
    "        directions = [(0,1,\"U\",\"D\"), (0,-1,\"D\",\"U\"), (1,0,\"L\",\"R\"), (-1,0,\"R\",\"L\")]\n",
    "        visited = set()\n",
    "        findtarget = False\n",
    "        endx, endy = -1, -1\n",
    "        # 从初始位置 dfs搜索整个图 \n",
    "        # 假设初始位置是在100,100 可以有效防止下标越界\n",
    "        dfs(100,100)\n",
    "        if not findtarget: # 没能找到target直接返回-1\n",
    "            return -1\n",
    "\n",
    "        # Dijkstra找到最短距离\n",
    "        heap = [(0,100,100)] # 初始位置\n",
    "        visited = set()\n",
    "        while len(heap):\n",
    "            cost, curx, cury = heapq.heappop(heap)\n",
    "            if (curx, cury) == (endx, endy): # 找到了 \n",
    "                return cost\n",
    "            if (curx, cury) in visited: # 避免重复访问\n",
    "                continue\n",
    "            visited.add((curx, cury))  # 标记已经访问\n",
    "            for dx, dy, _, _ in directions:\n",
    "                nxtx, nxty = curx+dx, cury+dy \n",
    "                # 节点没有越界 可以访问且也没有被访问过\n",
    "                if (0<=nxtx<=200 and 0 <=nxty<=200 and \n",
    "                    (nxtx, nxty) not in visited and \n",
    "                    grid[nxtx][nxty]): \n",
    "                    heapq.heappush(heap, (cost+grid[nxtx][nxty], nxtx, nxty))  # 加入最小堆\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "direc = {\"U\": [-1, 0], \"D\": [1, 0], \"L\": [0, -1], \"R\": [0, 1]}\n",
    "back = {\"U\": \"D\", \"L\": \"R\", \"D\": \"U\", \"R\": \"L\"}\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def findShortestPath(self, master: 'GridMaster') -> int:\n",
    "\n",
    "        def dfs(x, y):\n",
    "            nonlocal visit, target_x, target_y\n",
    "            if (x, y) in visit:\n",
    "                return\n",
    "            visit.add((x, y))\n",
    "            if master.isTarget():\n",
    "                target_x, target_y = x, y\n",
    "            for d in direc:\n",
    "                i, j = x + direc[d][0], y + direc[d][1]\n",
    "                if master.canMove(d):\n",
    "                    # 回溯\n",
    "                    dct[(x, y)][(i, j)] = master.move(d)\n",
    "                    dfs(i, j)\n",
    "                    dct[(i, j)][(x, y)] = master.move(back[d])\n",
    "            return\n",
    "        \n",
    "        # 深搜递归建图\n",
    "        n = 200\n",
    "        dct = defaultdict(dict)\n",
    "        start_x = start_y = n\n",
    "        target_x = target_y = -n\n",
    "        visit = set()\n",
    "        dfs(start_x, start_y)\n",
    "        if target_x == target_y == -n:\n",
    "            return -1\n",
    "        if start_x == start_y == target_y == target_x:\n",
    "            return 0\n",
    "        \n",
    "        # 最短路径搜索\n",
    "        stack = [[0, start_x, start_y]]\n",
    "        visit = set()\n",
    "        while stack:\n",
    "            dis, x, y = heapq.heappop(stack)\n",
    "            if (x, y) in visit:\n",
    "                continue\n",
    "            visit.add((x, y))\n",
    "            if (x, y) == (target_x, target_y):\n",
    "                return dis\n",
    "            for a, b in dct[(x, y)]:\n",
    "                heapq.heappush(stack, [dis + dct[(x, y)][(a, b)], a, b])\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# \"\"\"\n",
    "# This is GridMaster's API interface.\n",
    "# You should not implement it, or speculate about its implementation\n",
    "# \"\"\"\n",
    "#class GridMaster(object):\n",
    "#    def canMove(self, direction: str) -> bool:\n",
    "#        \n",
    "#\n",
    "#    def move(self, direction: str) -> int:\n",
    "#        \n",
    "#\n",
    "#    def isTarget(self) -> None:\n",
    "#        \n",
    "#\n",
    "\n",
    "from queue import PriorityQueue\n",
    "\n",
    "class Solution(object):\n",
    "    def findShortestPath(self, master: 'GridMaster') -> int:\n",
    "\n",
    "        vals = {}\n",
    "        vals[(0, 0)] = 0\n",
    "\n",
    "        t_i, t_j = None, None\n",
    "        def dfs(ii, jj):\n",
    "            nonlocal t_i, t_j\n",
    "            if master.isTarget():\n",
    "                t_i, t_j = ii, jj\n",
    "\n",
    "            if (ii-1, jj) not in vals and master.canMove('U'):\n",
    "                vals[(ii-1, jj)] = master.move('U')\n",
    "                dfs(ii-1, jj)\n",
    "                master.move('D')\n",
    "\n",
    "            if (ii+1, jj) not in vals and master.canMove('D'):\n",
    "                vals[(ii+1, jj)] = master.move('D')\n",
    "                dfs(ii+1, jj)\n",
    "                master.move('U')\n",
    "                \n",
    "            if (ii, jj-1) not in vals and master.canMove('L'):\n",
    "                vals[(ii, jj-1)] = master.move('L')\n",
    "                dfs(ii, jj-1)\n",
    "                master.move('R')\n",
    "                \n",
    "\n",
    "            if (ii, jj+1) not in vals and master.canMove('R'):\n",
    "                vals[(ii, jj+1)] = master.move('R')\n",
    "                dfs(ii, jj+1)\n",
    "                master.move('L')\n",
    "                \n",
    "        dfs(0, 0)\n",
    "        if t_i is None:\n",
    "            return -1;\n",
    "\n",
    "        que = PriorityQueue()\n",
    "        que.put((0, 0, 0))\n",
    "        best = {}\n",
    "        best[(0, 0)] = 0\n",
    "\n",
    "        while que.qsize():\n",
    "            cost, i, j = que.get()\n",
    "            if (i,j) == (t_i, t_j):\n",
    "                return cost\n",
    "\n",
    "            for ii, jj in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:\n",
    "                if (ii, jj) in vals and ((ii, jj) not in best or cost + vals[(ii, jj)] < best[(ii, jj)]):\n",
    "                    best[(ii, jj)] = cost + vals[(ii, jj)]\n",
    "                    que.put((cost + vals[(ii, jj)], ii, jj))\n",
    "\n",
    "        return -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
